import java.sql.CallableStatement;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Stack;
import java.util.WeakHashMap;
class  ListNode{
    int val;
    ListNode next;
    public ListNode(int val){
        this.val = val;
    }
}

public class Main{
    public static void main(String[] args) {
        ListNode head1 = new ListNode(9);
        ListNode cur = head1;
        cur.next = new ListNode(3);
        cur = cur.next;
        cur.next = new ListNode(7);
        int[] arr2 = {6,3};
        ListNode head2 = new ListNode(6);
        head2.next = new ListNode(3);
        addInList(head1,head2);
    }
    public static ListNode addInList (ListNode head1, ListNode head2) {
        ListNode tmp1 = head1;
        Stack<ListNode> stack1 = new Stack<>();
        while(tmp1 != null){
            stack1.push(tmp1);
            tmp1 = tmp1.next;
        }
        ListNode tmp2 = head2;
        Stack<ListNode> stack2 = new Stack<>();
        while(tmp2 != null){
            stack2.push(tmp2);
            tmp2 = tmp2.next;
        }
        if(stack1.isEmpty() ||  stack2.isEmpty()){
            return stack1.isEmpty() ? head2 : head1;
        }
        ListNode newHead = new ListNode(-1);
        int carry = 0;
        while(!stack1.isEmpty() && !stack2.isEmpty()){
            ListNode cur1 = stack1.pop();
            ListNode cur2 = stack2.pop();
            int num = cur1.val + cur2.val;
            num += carry;
            if(num > 9){
                carry = num /10;
            }
            ListNode node = new ListNode(num%10);
            if(newHead.next == null){
                newHead.next = node;
            }else{
                node.next = newHead.next;
                newHead.next = node;
            }
        }
        if(!stack1.isEmpty()){
            int num = stack1.pop().val + carry;
            if(num > 9){
                carry /= 10;
            }
            ListNode node = new ListNode(num%10);
            node.next = newHead.next;
            newHead.next = node;
        }
        if(!stack2.isEmpty()){
            int num = stack2.pop().val + carry;
            if(num > 9){
                carry /=10;
            }
            ListNode node = new ListNode(num%10);
            node.next = newHead.next;
            newHead.next = node;
        }
        if(carry > 0){
            ListNode node = new ListNode(carry);
            node.next = newHead.next;
            newHead.next = node;
        }
        return newHead.next;
    }
}


//public class Main{
//    public static void main(String[] args) throws InterruptedException {
//        final Object obj = new Object();
//        Thread t1 = new Thread(){
//            @Override
//            public void run() {                    try{
//                obj.wait();
//                System.out.println("t1");
//            }catch (InterruptedException e){
//                e.printStackTrace();
//            }
//            }
//        }
//    };
//        t1.start();
//        Thread.sleep(1000);
//    Thread t2 = new Thread(){
//        @Override
//        public void run() {
//            synchronized(obj){
//                obj.notifyAll();
//                System.out.println("t2");
//            }
//        }
//    };
//        t2.start();
//                synchronized (obj){
//
//    }
//}



//public class Main{
//
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNextLine()){
//            String str = sc.nextLine();
//            StringBuffer sb = new StringBuffer();
//            int count = 0;
//            int quota = 0;
//            for(int i = 0;i<str.length();i++){
//                char ch = str.charAt(i);
//                if(ch == '\"'){
//                    quota++;
//                }else if(ch != ' '){
//                    sb.append(ch);
//
//                }else if(quota % 2 == 0){
//                    sb.append("\n");
//                    count++;
//                }else{
//                    sb.append(' ');
//                }
//            }
//            System.out.println(count+1);
//            System.out.println(sb.toString());
//        }
//        sc.close();
//
//    }
//
//
//}




//public class Main {
//    public static void main(String[] args) {
//        B b =new B();
//        System.out.println(b.getValue());
//    }
//    static class A{
//        protected  int value;
//        public A(int v){
//            setValue(v);
//        }
//        public void setValue(int value){
//            this.value = value;
//        }
//        public int getValue(){
//            try {
//                value++;
//                return value;
//            }catch (Exception e){
//                System.out.println(e.toString());
//            }finally {
//                this.setValue(value);
//                System.out.println(value);
//            }
//            return value;
//        }
//    }
//    static class B extends A{
//        public B(){
//            super(5);
//            setValue(getValue()-3);
//        }
//        public void setValue(int value){
//            super.setValue(2 * value);
//        }
//    }
//}
